package com.lx.algorithm.code.xly3.class04;


import com.lx.algorithm.Utils;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-10 16:45:43
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-10     张李鑫                     1.0         1.0 Version
 */
public class Code04 {
    /**
     * 最长递增子序列问题的O(N*logN)的解法
     */


    /**
     * 用一个ends数组去加速记录
     *
     * @param arr
     * @return
     */
    public static int dp(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int[] dp = new int[arr.length];
        int[] ends = new int[arr.length];
        dp[0] = 1;
        ends[0] = arr[0];
        int right = 0;
        //二分左右边界
        int l = 0;
        int r = 0;
        int mid = 0;
        for (int i = 1; i < dp.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                mid = (l + r) / 2;
                if (arr[i] > ends[mid]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            //比较l是否越过原来的右边界 如果越过说明 扩了
            right = Math.max(l, right);
            //记录ends数组
            ends[l] = arr[i];
            //当前值的最大前缀就是索引+1
            dp[i] = l + 1;
        }
        return dp[arr.length - 1];
    }



    public static void main(String[] args) {
        int[] arr = Utils.generateRandomMatrix(20);
        System.out.println(dp(arr));
    }
}
